Problems tagged with "aggregate analysis"

Consider the code below, which is a modification of the code for bfs given in lecture:

from collections import deque

def modified_full_bfs(graph):
    status = {node: 'undiscovered' for node in graph.nodes}
    for node in graph.nodes:
        if status[node] == 'undiscovered':
            modified_bfs(graph, node, status)

def modified_bfs(graph, source, status=None):
    """Start a BFS at `source`."""
    if status is None:
        status = {node: 'undiscovered' for node in graph.nodes}

    status[source] = 'pending'
    pending = deque([source])

    # while there are still pending nodes
    while pending: 
        u = pending.popleft()
        for v in graph.neighbors(u):
            # explore edge (u,v)
            if status[v] == 'undiscovered':
                status[v] = 'pending'
                # append to right
                pending.append(v)
                for z in graph.nodes:   # <----- new line!
                    print(z, status[z]) # <----- new line!

        status[u] = 'visited'

Notice the two new lines; these lines print all node statuses any time that an undiscovered node has been found.

What is the time complexity of this modified modified_full_bfs? State your answer in asymptotic notation in terms of the number of nodes, \(|V|\), and the number of edges, \(|E|\). You may assume that the graph is represented using an adjacency list.

Suppose an undirected graph \(G = (V, E)\) is a tree with 33 edges. Suppose a node \(s\) is used as the source of a depth-first search.

Including the root call of dfs on node \(s\), how many calls to dfs will be made?

Suppose a graph \(G = (V, E)\) is stored using an adjacency list representation in the variable adj_list. What is the time complexity of the below code?

for lst in adj_list:
    for u in lst:
        print(u)

Consider the code shown below. It shows DFS as seen in lecture, with one modification: a print statement in the for-loop.

def dfs(graph, u, status=None):
    """Start a DFS at `u`."""
    # initialize status if it was not passed
    if status is None:
        status = {node: 'undiscovered' for node in graph.nodes}
    status[u] = 'pending'
    for v in graph.neighbors(u):
        print("Hello!")
        if status[v] == 'undiscovered':
            dfs(graph, v, status)
    status[u] = 'visited'

How many times will "Hello!" be printed if dfs is run on the graph below using node \(u\) as the source? Note that dfs will not be restarted if the first call does not explore the whole graph.

A ``hub and spoke'' graph with \(n\) nodes consists of a single ``hub'' node \(h\) along with \(n - 1\) ``spoke'' nodes, \(u_1, \ldots, u_{n-1}\) and \(n - 1\) edges from the hub node \(h\) to each of the spoke nodes. For example, a ``hub and spoke'' graph with 8 nodes looks like the below:

What is the worst case time complexity of an optimal algorithm which takes as input an arbitrary graph \(G = (V, E)\) and determines if it is a ``hub and spoke'' graph? You may assume that the graph is represented as an adjacency list and that the total number of edges in the graph can be retrieved in constant time.

Suppose the code below is run on a graph \(G = (V, E)\). What is its time complexity? You may assume that \(|E| \geq 1\).

for u in graph.nodes:
    for v in graph.neighbors(u):
        print(u, v)